3350. Adjacent Increasing Subarrays Detection II

Medium

題目描述

Description

Given an array nums of n integers, your task is to find the maximum value of k for which there exist two adjacent subarrays of length k each, such that both subarrays are strictly increasing. Specifically, check if there are two subarrays of length k starting at indices a and b (a < b), where:

• Both subarrays nums[a..a + k - 1] and nums[b..b + k - 1] are strictly increasing.
• The subarrays must be adjacent, meaning b = a + k.

Return the maximum possible value of k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [2,5,7,8,9,2,3,4,3,1]
Output: 3
Explanation:

• The subarray starting at index 2 is [7, 8, 9], which is strictly increasing.
• The subarray starting at index 5 is [2, 3, 4], which is also strictly increasing.
• These two subarrays are adjacent, and 3 is the maximum possible value of k for which two such adjacent strictly increasing subarrays exist.

Example 2:

Input: nums = [1,2,3,4,4,4,4,5,6,7]
Output: 2 Explanation:

• The subarray starting at index 0 is [1, 2], which is strictly increasing.
• The subarray starting at index 2 is [3, 4], which is also strictly increasing.
• These two subarrays are adjacent, and 2 is the maximum possible value of k for which two such adjacent strictly increasing subarrays exist.

Constraints:

• 2 <= nums.length <= 2 * 105
• -109 <= nums[i] <= 109

解答

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxIncreasingSubarrays = function (nums) {
  if (nums.length <= 1) {
    return 0;
  }

  let count = 1;
  let preCount = 0;
  let result = 1;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > nums[i - 1]) {
      count++;
    } else {
      result = Math.max(result, Math.floor(count / 2));
      result = Math.max(result, Math.min(count, preCount));
      preCount = count;
      count = 1;
    }
  }

  result = Math.max(result, Math.floor(count / 2));
  result = Math.max(result, Math.min(count, preCount));

  return result;
};

解題思路

與 上一題 不同的是這次題目沒有給 k，而是變成題目要找出最大的 k，且兩個相鄰的 subarray 也都要是 strictly increasing。

1. 首先由於測試範圍是 2 <= nums.length <= 2 * 105，故在最小的 nums.length = 2 時直接 return 0。
   以及宣告變數
   • count 來記錄當前的 k
   • preCount 來紀錄前一段的 k
   • result 來紀錄最終的答案 (最大的 k )。

if (nums.length <= 1) {
  return 0;
}

let count = 1;
let preCount = 0;
let result = 1;

2. 接著遍歷陣列，如果下一個數字大於現在的數字，代表目前 strictly increasing，將 count 加一，否則就更新 result。

for (let i = 1; i < nums.length; i++) {
  if (nums[i] > nums[i - 1]) {
    count++;
  } else {
    result = Math.max(result, Math.floor(count / 2));
    result = Math.max(result, Math.min(count, preCount));
    preCount = count; // 將 preCount 更新為當前的 count
    count = 1; // 重置 count
  }
}

更新 result 的步驟

Math.floor(count / 2)

Math.floor(count / 2) 是用來處理「單一區段連續遞增」的情況。

假設 nums = [1, 2, 3, 4, 5, 6]，這裡的 count = 6。 且因為這一整段是遞增的，所以可以被切成兩個長度為 3 的子陣列：

• [1, 2, 3]
• [4, 5, 6]

所以這段裡面最大的 k 可以是 count / 2 = 3。（如果長度是奇數，比如 5，那最大可切成 Math.floor(5 / 2) = 2。）

Math.min(count, preCount)

Math.min(count, preCount) 是用來處理「有斷掉」的情況。

假設 nums = [2, 3, 4, 5, 1, 2, 3]

這整段不是 strictly increasing，中間有斷掉，故可以拆成

• [2, 3, 4, 5] // count = 4
• [1, 2, 3] // count = 3，preCount = 4

而形成的最大 k 是兩段中「較短」的那一段長度，故上述例子的最大 k 為 3。

3. 而 for 迴圈結束後最後一段遞增區間還沒被結算

   假設 nums = [1, 2, 3, 4, 5]，迴圈跑完時，count = 5，但因為從頭到尾沒遇到遞增中斷，else 從未執行

因此最後再判斷一次即可。

result = Math.max(result, Math.floor(count / 2));
result = Math.max(result, Math.min(count, preCount));

return result;

心得

複雜死ㄌ：（
一直鬼打牆瘋狂看解析才搞懂原理。